package leetcode.code1163;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

import leetcode.IDebug;
import leetcode.helper.H;

public class SolutionSort implements IDebug {

	public String lastSubstring(String s) {
		return s.substring(sa(s));
	}

	int N = 400010;// 30010
	int[] x = new int[N], y = new int[N], c = new int[N];
	int[] sa = new int[N], rk = new int[N], height = new int[N];

	public int sa(String s) {
		int n = s.length(), m = 128;
		s = " " + s;
		char[] cs = s.toCharArray();
		// sa：两遍基数排序，板子背不下来也可以直接使用 sort，复杂度退化到 n \log^2 n
		for (int i = 1; i <= n; i++) {
			x[i] = cs[i];
			c[x[i]]++;
		}
		for (int i = 2; i <= m; i++)
			c[i] += c[i - 1];
		for (int i = n; i > 0; i--)
			sa[c[x[i]]--] = i;
		for (int k = 1; k <= n; k <<= 1) {
			int cur = 0;
			for (int i = n - k + 1; i <= n; i++)
				y[++cur] = i;
			for (int i = 1; i <= n; i++) {
				if (sa[i] > k)
					y[++cur] = sa[i] - k;
			}
			for (int i = 1; i <= m; i++)
				c[i] = 0;
			for (int i = 1; i <= n; i++)
				c[x[i]]++;
			for (int i = 2; i <= m; i++)
				c[i] += c[i - 1];
			for (int i = n; i > 0; i--) {
				sa[c[x[y[i]]]--] = y[i];
				y[i] = 0;
			}
			swap(x, y);
			x[sa[1]] = cur = 1;
			for (int i = 2; i <= n; i++) {
				if (y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k])
					x[sa[i]] = cur;
				else
					x[sa[i]] = ++cur;
			}
			if (cur == n)
				break;
			m = cur;
		}
//		for (int i = 1; i <= n; i++) {
//			System.out.println(i + " " + s.substring(sa[i]) + " " + sa[i]);
//		}
//		System.out.println(sa[n]);
		return sa[n] - 1;
	}

	void swap(int[] a, int[] b) {
		int n = a.length;
		int[] c = a.clone();
		for (int i = 0; i < n; i++)
			a[i] = b[i];
		for (int i = 0; i < n; i++)
			b[i] = c[i];
	}

	@Override
	public void debug4() {
//		H.compare("xxxiib", this.lastSubstring(
//				"bababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababa"));
//		H.compare("xxxiib", this.lastSubstring("xxxiiaxxxiib"));
		H.compare("xxbx", this.lastSubstring("xxbbxxbx"));
		H.compare("bab", this.lastSubstring("abab"));

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		SolutionSort so = new SolutionSort();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();

	}

}
